package cn.lbd.arithmetic.leetcode.editor.cn;
//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
//
// 
//
// 示例： 
//
// 输入：1->2->4, 1->3->4
//输出：1->1->2->3->4->4
// 
// Related Topics 链表 
// 👍 1284 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/*class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                '}';
    }
}



class Solution21 {
    //对链表的一趟归并排序
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode tempL1 = l1.next;
        ListNode tempL2 = l2.next;
        ListNode result = new ListNode(0);
        *//*ListNode result = tempL1.val <= tempL2.val ? tempL1 : tempL2;*//*
        ListNode temp = result;
        while (tempL1 != null && tempL2 != null) {
            if (tempL1.val <= tempL2.val){
                temp.next = tempL1;
                tempL1 = tempL1.next;
                temp = temp.next;
            }else {
                temp.next = tempL2;
                tempL2 = tempL2.next;
                temp = temp.next;
            }
        }
        while(tempL2 != null) {
            temp.next = tempL2;
            tempL2 = tempL2.next;
            temp = temp.next;
        }
        while(tempL1 != null) {
            temp.next = tempL1;
            tempL1 = tempL1.next;
            temp = temp.next;
        }
        return result;
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode5 = new ListNode(2);
        ListNode listNode7 = new ListNode(4);
        SingleLinkedList list1 = new SingleLinkedList();
        list1.add(listNode1);
        list1.add(listNode5);
        list1.add(listNode7);
        list1.list();
        System.out.println();
        ListNode listNode2 = new ListNode(1);
        ListNode listNode4 = new ListNode(3);
        ListNode listNode8 = new ListNode(4);
        ListNode listNode9 = new ListNode(9);
        SingleLinkedList list2 = new SingleLinkedList();
        list2.add(listNode2);
        list2.add(listNode4);
        list2.add(listNode8);
        list2.add(listNode9);
        list2.list();
        System.out.println();
        ListNode head = mergeTwoLists(list1.getHead(), list2.getHead());
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        ListNode temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }

    }
}

class SingleLinkedList {

    //头节点
    private ListNode head = new ListNode(0);

    public ListNode getHead(){
        return head;
    }

    //添加节点到单向链表尾部
    public void add(ListNode heroNode) {
        ListNode temp = head;
        while (true) {
            //找到链表的最后一个节点
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = heroNode;
    }

    //显示链表
    public void list() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }

        ListNode temp = head.next;

        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }


}*/
//leetcode submit region end(Prohibit modification and deletion)
